package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.ListNode;

/**
 * 翻转链表
 */
@LeetCodeExplore
@Easy
public class ReverseLinkedList {

    public ListNode reverse(ListNode head) {
        ListNode newHead = null;

        // 头插法:
        //
        // 1 -> 2 -> 3 -> 4
        // ↑
        //
        // 1 -> NULL
        // ↑
        // 2 -> 3 -> 4
        // ↑
        //
        // 2 -> 1 -> NULL
        // ↑
        // 3 -> 4
        // ↑
        while (head != null) {
            ListNode temp = head.next; // 剩下的

            head.next = newHead;
            newHead = head;

            head = temp;
        }

        return newHead;
    }

    // ==========================
    // 递归
    // ==========================

    public ListNode reverseList(ListNode head) {
        return reverseListInt(head, null);
    }

    private ListNode reverseListInt(ListNode head, ListNode newHead) {
        // 结束条件，当 head 为空的时候，整个链表也翻转完毕了
        if (head == null)
            return newHead;

        ListNode next = head.next;
        head.next = newHead;
        return reverseListInt(next, head);
    }

}
